Introduction to Binary Search and implementation of the iterative algorithm.
Codes:
- Example
This track of the course covers the topic "Searching".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Searching Algorithms.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
Introduction to Binary Search and implementation of the iterative algorithm.
Codes:
Recursive binary search implementation and comparison with iterative binary search is discussed.
Codes:
Time Complexity analysis of Binary Search is discussed
Given a sorted array with repetition and an element x, we need to find index of first occurrence of x.
Codes:
Given a sorted array with repetition and an element x, we need to find index of last occurrence of x.
Codes:
Given a sorted array and an element x, we need to count occurrences of x in the array.
Codes:
Given a sorted binary array, we need to count 1s in this array. This video talks about two solutions.
Codes:
Given an integer, we need to find floor of its square root. This video talks about two methods.
Codes:
Given an infinite sized array, we need to write an efficient solution to search an element. In this video, we have discussed two solutions.
Codes:
This video talks about O(Log n) approach to search an element in a sorted and rotated array.
Codes:
This video talks about two solutions of the problem.
Codes:
The videos discusses two approaches to solve the problem.
Codes:
Majority element is an element that appears more than n/2 times in an array of size n. In this video, two methods to find majority element in an array are discussed.
Codes:
Repeating Elements
Codes:
Repeating Elements Part (2)
Codes:

Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
key = 110;
Output : 6
Element 110 is present at index 6
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
key = 175;
Output : -1
Element 175 is not present in arr[].

mid1 = l + (r-l)/3
mid2 = r – (r-l)/3

binary_search(start_ptr, end_ptr, ele)
15 exists in vector
20 exists in Array
upper_bound(first_itr, last_itr, ele)
Input : 10 20 30 30 40 50
Output : upper_bound for element 30 will return
an iterator pointing to the element 40.
Input : 10 20 30 40 50
Output : upper_bound for element 45 will return
an iterator pointing to the element 50.
Input : 10 20 30 40 50
Output : upper_bound for element 60 will
return end iterator.
Vector contains : 10 20 30 40 50
Upper_bound for element 35 is at position : 3
Upper_bound for element 45 is at position : 4
Array contains : 10 20 30 40 50
upper_bound for element 35 is at position : 3
upper_bound for element 45 is at position : 4
lower_bound(first_itr, last_itr, ele)
Vector contains : 10 20 30 40 50
lower_bound for element 20 at position : 1
lower_bound for element 55 at position : 5
Array contains : 10 20 30 40 50
lower_bound for element 20 is at position : 1
lower_bound for element 55 is at position : 5
public static int binarySearch(data_type arr, data_type key )
Searching for 35 in byteArr[] = {10,20,15,22,35}
will give result as 4 as it is the index of 35
Searching for 35 in charArr[] = {'g','p','q','c','i'}
will give result as 1 as it is the index of 'g'
Searching for 22 in intArr[] = {10,20,15,22,35};
will give result as 3 as it is the index of 22
Searching for 1.5 in doubleArr[] = {10.2,15.1,2.2,3.5}
will give result as -1 as it is the insertion point of 1.5
Searching for 35.0 in floatArr[] = {10.2f,15.1f,2.2f,3.5f}
will give result as -5 as it is the insertion point of 35.0
Searching for 5 in shortArr[] = {10,20,15,22,35}
will give result as -1 as it is the insertion point of 5
35 found at index = 4
g found at index = 1
22 found at index = 3
1.5 found at index = -1
35.0 found at index = -5
5 found at index = -1
// Returns index of key in sorted list sorted in
// ascending order
public static int binarySearch(List slist, T key)
// Returns index of key in sorted list sorted in
// order defined by Comparator c.
public static int binarySearch(List slist, T key, Comparator c)
If key is not present, the it returns "(-(insertion point) - 1)".
The insertion point is defined as the point at which the key
would be inserted into the list.
3
-5
Found at index 1
Note: Arrays.binarysearch() works for arrays which can be of primitive data type also. Collections.binarysearch() works for objects Collections like ArrayList and LinkedList.
Input
[2, 3, 2, 1, 5]
Output
4 2
1) Sort the input array.Time Complexity : O(nLogn)
2) Traverse the array and check for missing and repeating.
Example Array : [2, 3, 2, 1, 5]
S = 13
(n *(n+1))/2 = 15
13 = 15 - x + y
x - y = 2 .... 1
P = 60
1*2*3..n = 120
60 = (120*y)/x
x = 2y .... 2
Solving Equation 1 and 2 --
x = 4 and y = 2
//n : size of arrayTime Complexity: O(n)
void repeating_missing(arr, n)
{
count[n+1] = {0}
for (i=0 to n-1 )
count[a[i]]++
for (i=1 to n) {
if (count[i] == 0 )
missing = i
if (count[i] == 2 )
repeating = i
}
print(repeating, missing)
}
//n : size of arrayTime Complexity: O(n)
void repeating_missing(arr, n)
{
for ( i=0 to n-1 ) {
temp = arr[abs(arr[i])- 1]
if (temp < 0 ) {
repeating = abs(arr[i])
break
}
arr[abs(arr[i])- 1] = -arr[abs[arr(i)]- 1]
}
for (i=0 to n-1) {
if (arr[i] > 0 )
missing = i+1
}
print(repeating, missing)
}
Input : [1, 1, 2, 2, 2, 2, 3] , x = 2Solution : Linear Search We can traverse the array and count the number of occurences of x in the given input array.
Output : 4
int first_index(arr, low, high, x, n)Time Complexity : O(Log(n))
{
if(high >= low)
{
mid = (low + high)/2 /*low + (high - low)/2*/
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x) :
return mid
else if(x > arr[mid]) :
return first_index(arr, (mid + 1), high, x, n)
else :
return first_index(arr, low, (mid -1), x, n)
}
}
int last_index(arr, low, high, x, n):
{
if (high >= low)
{
int mid = (low + high)/2 /*low + (high - low)/2*/
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid
else if(x < arr[mid]) :
return last_index(arr, low, (mid -1), x, n)
else :
return last_index(arr, (mid + 1), high, x, n)
}
}
int count_occurences(arr, n, x)
{
i = first_index(arr, 0, n-1, x, n)
j = last_index(arr, 0, n-1, x, n)
count = j-i + 1
return count
}
Input : arr[] = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1]Solution - One simple solution can be traverse the Array and find out the first index of 1. Since the array is sorted, we can optimize the solution using binary search by reducing the effective search space in each step.
Output : 6
The index of first 1 in the array is 6.
int indexOfFirstOne(arr[], low, high)Time Complexity : O(Log(n))
{
while (low <= high)
{
int mid = (low + high) / 2
if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0)) :
return mid
else if (arr[mid] == 1) :
high = mid - 1
else :
low = mid + 1
}
}
Input : [10, 20, 15, 2, 23, 90, 67]Solution : A simple solution is to traverse the array and as soon as we find a peak element, we return it. The worst case time complexity of this method would be O(n).Can we find a peak element in worst time complexity better than O(n)?
Output : 20 or 90

int findPeak(arr[], low, high, n)Time Complexity : O(Log(n))
{
int mid = low + (high - low)/2 /* (low + high)/2 */
if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
(mid == n-1 || arr[mid+1] <= arr[mid])) :
return arr[mid]
// If middle element is not peak and its left neighbour is greater
// than it, then left half must have a peak element
else if (mid > 0 && arr[mid-1] > arr[mid]) :
return findPeak(arr, low, (mid -1), n)
// If middle element is not peak and its right neighbour is greater
// than it, then right half must have a peak element
else :
return findPeak(arr, (mid + 1), high, n)
}
Asked In: Paytm
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon
A | T(n) = 2T(n/2) + O(1) and T(1) = T(0) = O(1) |
B | T(n) = T(n-1) + O(1) and T(1) = T(0) = O(1) |
C | T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1) |
D | T(n) = T(n-2) + O(1) and T(1) = T(0) = O(1) |